# 借鉴这个代码  https://github.com/gycg/Algorithm/blob/master/heap_sort.py
import math


def parent(i):
    return math.floor(i/2)


def left(i):
    return 2*i+1


def right(i):
    return 2*i+2


# 维护最大堆性质
def max_heapify(A, i, heap_size):
    l = left(i)
    r = right(i)
    if l < heap_size and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < heap_size and A[r] > A[largest]:
        largest = r
    if largest != i:
        temp = A[i]
        A[i] = A[largest]
        A[largest] = temp
        max_heapify(A, largest, heap_size)


def build_max_heap(A, heap_size):
    for i in range(math.floor(heap_size/2), -1, -1):
        max_heapify(A, i, heap_size)


def heap_sort(A):
    heap_size = len(A)
    build_max_heap(A, heap_size)
    for i in range(len(A)-1, 0, -1):
        temp = A[0]
        A[0] = A[i]
        A[i] = temp
        heap_size = heap_size-1
        max_heapify(A, 0, heap_size)


A = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
heap_sort(A)
print(A)



